Цель 🎯
- Задача: Найти оптимальный маршрут от исходного сервера `S` ко всем другим серверам.
- Результат: Для каждого сервера `i` необходимо вычислить:
- Общая задержка: Минимальная стоимость (кратчайший путь) от `S` до `i`.
- Следующий узел: *Первый сервер* на этом кратчайшем пути.
- Пример: Если лучший путь от `S` до `D` — это `S -> A -> B -> D`, то **Следующий узел** — это `A`.
Сеть 💾
Мы будем использовать список смежности для хранения сети.
- Серверы — это узлы.
- Соединения — это двунаправленные рёбра.
- Задержка — это положительный вес.
// Связи: 0-1 (10 мс), 0-2 (3 мс)
adj = [
0:[(1, 10), (2, 3)],
1:[(0, 10)],
2:[(0, 3)],
...
]
adj = [
0:[(1, 10), (2, 3)],
1:[(0, 10)],
2:[(0, 3)],
...
]
Формат вывода ⚙️
Необходимо вывести `V` строк. Строка `i` соответствует серверу `i`.
[задержка] [следующий_узел]Для достижимого узла.
0 -1Если узел — сам источник `S`.
-1 -1Если узел недостижим из `S`.